#include "MLCluStream.h"
#include "MLClustering_KMeans.h"
#include "MLGlobals.h"
using namespace mylablib;


///////////////////////////////////////////////////////////////////////////
// CMLCluStreamMicroCluster
CMLCluStreamMicroCluster::CMLCluStreamMicroCluster()
{
	m_pDistFunc = NULL;
	m_pClustering = NULL;
}

CMLCluStreamMicroCluster::~CMLCluStreamMicroCluster()
{
}

int CMLCluStreamMicroCluster::Create(const CMLDataSet& dataSet, CMLCluStream* pClustering, int nId, int nTimeStamp)
{
	int i;
	m_nId = nId;
	m_pClustering = pClustering;
	m_vLS.zero();
	m_vSS.zero();
	m_dTimeStampLS = 0;
	m_dTimeStampSS = 0;
	m_nDataPointCount = 0;

	m_vTimeStamps.clear();

	if (dataSet.IsEmpty())
		return 0;

	// Insert all the data points
	for (i=0; i<dataSet.Count(); i++)
		Absorb(dataSet.Get(i), nTimeStamp);

	return 0;
}

int CMLCluStreamMicroCluster::Merge(const CMLCluStreamMicroCluster* pMicroCluster)
{
	m_vLS.add(pMicroCluster->m_vLS);
	m_vSS.add(pMicroCluster->m_vSS);
	m_nDataPointCount += pMicroCluster->GetDataPointCount();
	return 0;
}

int CMLCluStreamMicroCluster::Absorb(const CMLDataPoint& p, int nTimeStamp)
{
	m_nDataPointCount++;
	m_vLS.add(p);
	m_vSS.add(p^2);
	m_dTimeStampLS += (double)nTimeStamp;
	m_dTimeStampSS += (double)nTimeStamp*nTimeStamp;
	if ((int)m_vTimeStamps.size() >= m_pClustering->GetNumLastTimeCheck())
	{
		m_dTimeStampLS -= m_vTimeStamps.front();
		m_dTimeStampLS -= m_vTimeStamps.front()*m_vTimeStamps.front();
		m_vTimeStamps.push_back(nTimeStamp);
		m_vTimeStamps.pop_front();
	}

	return 0;
}

///////////////////////////////////////////////////////////////////////////
// CMLCluStreamMicroCluster
CMLCluStreamSnapshot::CMLCluStreamSnapshot(void)
{
}

CMLCluStreamSnapshot::~CMLCluStreamSnapshot(void)
{
	Clear();
}

CMLCluStreamSnapshot::CMLCluStreamSnapshot(const CMLCluStreamSnapshot& src)
{
	operator=(src);
}

const CMLCluStreamSnapshot& CMLCluStreamSnapshot::operator =(const CMLCluStreamSnapshot& src)
{
	int i;
	int nNum = src.GetNumCFs();

	Clear();

	for (i=0; i<nNum; i++)
	{
		CMicroClusterFeature_* pCF = new CMicroClusterFeature_();
		pCF->nId = src.GetCF(i)->nId;
		pCF->nNumDataPoints = src.GetCF(i)->nNumDataPoints;
		pCF->vLS = src.GetCF(i)->vLS;

		m_vCFs.push_back(pCF);
		m_mapCFs.insert(std::make_pair(pCF->nId, pCF));
	}
	return *this;
}

int CMLCluStreamSnapshot::Create(const std::vector<CMLCluStreamMicroCluster*>& vMicroClusters)
{
	int i;
	int nNum = (int)vMicroClusters.size();
	Clear();
	for (i=0; i<nNum; i++)
	{
		CMicroClusterFeature_* pCF = new CMicroClusterFeature_;
		pCF->nNumDataPoints = vMicroClusters[i]->GetDataPointCount();
		pCF->nId = vMicroClusters[i]->GetId();
		pCF->vLS = vMicroClusters[i]->GetLS();
		
		m_vCFs.push_back(pCF);
		m_mapCFs.insert(std::make_pair(pCF->nId, pCF));
	}
	return 0;
}

int CMLCluStreamSnapshot::Clear(void)
{
	int i;
	for (i=0; i<GetNumCFs(); i++)
	{
		delete m_vCFs[i];
	}
	m_vCFs.clear();
	m_mapCFs.clear();
	return 0;
}

int CMLCluStreamSnapshot::Subtract(const CMLCluStreamSnapshot& prevSnap)
{
	std::map<int, CMicroClusterFeature_*>::const_iterator Iter;
	for(Iter = m_mapCFs.begin(); Iter != m_mapCFs.end(); Iter++)
	{
		int nId = (*Iter).first;
		CMicroClusterFeature_* pCF = (*Iter).second;
		const CMicroClusterFeature_* pPrevCF = prevSnap.FindCF(nId);
		if (pPrevCF != NULL)
		{
			pCF->nNumDataPoints -= pPrevCF->nNumDataPoints;
			pCF->vLS.sub(pPrevCF->vLS);
		}
	}

	// Remove all the 0 data points micro-clusters
	int i;
	for (i=0; i<GetNumCFs(); i++)
	{
		if (m_vCFs[i]->nNumDataPoints <= 0)
		{
			delete m_vCFs[i];

			m_mapCFs.erase(m_vCFs[i]->nId);
			m_vCFs.erase(m_vCFs.begin() + i);
			i--;
		}
	}
	return 0;
}

///////////////////////////////////////////////////////////////////////////
// CMLCluStream
CMLCluStream::CMLCluStream(void)
{
	m_pDistFunc = mlglobals.GetEuclideanDistance();
	m_nDataPointInitNumber = 1;
	m_nDataPointTotalNumber = 0;
	m_dMaxMicroClusterRadius = 3.0;
	m_nTimeClock = 0;
	m_nMicroClusterIdCounter = 0;
}

CMLCluStream::~CMLCluStream(void)
{
}

int CMLCluStream::SetParameters(const std::wstring& wstrParams)
{
	return 0;
}

int CMLCluStream::Insert(const CMLDataPoint& dataPoint)
{
	int nRet;
	if (m_nDataPointTotalNumber < m_nDataPointInitNumber)
	{
		m_DataSet.Insert(dataPoint);
		if (m_nDataPointTotalNumber == m_nDataPointInitNumber -1)
		{
			// Do K-MEANS clustering to create micro-clusters
			nRet = InitMicroClusters();
			if (ML_FAILED(nRet))
				return nRet;
		}
		else
		{
			nRet = 0;
		}
	}
	else
	{
		// Insert to the MicroClusters
		nRet = InsertToMicroCluster(dataPoint);
		if (ML_FAILED(nRet))
			return nRet;

		//// Check the outlier
		nRet = CheckOutlierMicroCluster();
		if (ML_FAILED(nRet))
			return nRet;
	}
	m_nDataPointTotalNumber++;
	m_nTimeClock++;
	return nRet;
}

int CMLCluStream::GetClusters(const std::wstring& params, std::vector<CMLDataCluster>& vClusters)
{
	int nK = _wtoi(params.c_str());
	return CreateMacroClusters(nK, vClusters);
}

int CMLCluStream::CreateMacroClusters(int nK, std::vector<CMLDataCluster>& vClusters) const
{
	CMLCluStreamSnapshot snap;
	SaveSnapshot(snap);
	return  MacroClustering(nK, vClusters, snap);
}

int CMLCluStream::CreateMacroClusters(int nK, std::vector<CMLDataCluster>& vClusters, const CMLCluStreamSnapshot& prevSnap) const
{
	// Create current snapshot
	CMLCluStreamSnapshot snap;
	SaveSnapshot(snap);

	// Subtract
	snap.Subtract(prevSnap);

	// Create the dataset to prepare the clustering
	return  MacroClustering(nK, vClusters,  snap);
}

int CMLCluStream::InitMicroClusters()
{
	CMLClustering_KMeans kMeans;
	int nK = GetInitNumMicroClusters();

	// Initialize the k-means clustering method
	kMeans.SetDistanceFunc(GetDistanceFunc());
	kMeans.SetK(nK);

	// Use K-Means to create micro-clusters
	std::vector<CMLDataCluster> vClusters;
	int nRet = kMeans.DoClustering(m_DataSet, vClusters);
	if (ML_FAILED(nRet))
		return nRet;

	// Create the micro-clusters
	if (m_vpMicroClusters.empty() == false)
		ReleaseMicroClusters();
	m_vpMicroClusters.resize((size_t)nK);
	int i;
	for (i=0; i<nK; i++)
	{
		m_vpMicroClusters[i] = new CMLCluStreamMicroCluster();
		m_vpMicroClusters[i]->SetDistFunc(GetDistanceFunc());
		m_vpMicroClusters[i]->Create(vClusters[i].dataset, this, m_nMicroClusterIdCounter++, m_nTimeClock);
	}

	return 0;
}

int CMLCluStream::InsertToMicroCluster(const CMLDataPoint& dataPoint)
{
	int nRet;
	double dDist = 0;
	CMLCluStreamMicroCluster* pMicroCluster = FindNearestMicroCluster(dataPoint, dDist);

	if (pMicroCluster == NULL || dDist > m_dMaxMicroClusterRadius)
	{
		if (GetNumMicroClusters() >= m_nMaxNumMicroClusters)
		{
			// Merger two closest micro-cluster
			nRet = MergeClosestTwoMicroClusters();
			ML_ON_FAILED_RETURN(nRet);
		}

		// Create a new micro-cluster
		CMLDataSet dataSet;
		dataSet.Insert(dataPoint);
		CMLCluStreamMicroCluster* pNewMicroCluster = new CMLCluStreamMicroCluster();
		pNewMicroCluster->SetDistFunc(GetDistanceFunc());
		pNewMicroCluster->Create(dataSet, this, m_nMicroClusterIdCounter++, m_nTimeClock);
		m_vpMicroClusters.push_back(pNewMicroCluster);
	}
	else
	{
		// Insert into the micro-cluster
		nRet = pMicroCluster->Absorb(dataPoint, m_nTimeClock);
		if (ML_FAILED(nRet))
			return nRet;
	}
	return 0;
}


CMLCluStreamMicroCluster* CMLCluStream::FindNearestMicroCluster(const CMLDataPoint& point, double& dDist)
{
	int i;
	double dMinDist = DBL_MAX;
	CMLCluStreamMicroCluster* pNearestMicroCluster = NULL;
	for (i=0; i<(int)m_vpMicroClusters.size(); i++)
	{
		double dDist = m_pDistFunc->Distance(point, m_vpMicroClusters[i]->GetCenter());
		if (dDist < dMinDist)
		{
			pNearestMicroCluster = m_vpMicroClusters[i];
			dMinDist = dDist;
		}
	}
	dDist = dMinDist;
	return pNearestMicroCluster;
}

int CMLCluStream::MergeClosestTwoMicroClusters(void)
{
	// Find two closest clusters
	double dMinDist = DBL_MAX;
	CMLCluStreamMicroCluster* pCluster1 = NULL;
	CMLCluStreamMicroCluster* pCluster2 = NULL;
	int nIndex1, nIndex2;
	int nNumCluster = (int)m_vpMicroClusters.size();
	if (nNumCluster < 2)
		return -1;
	int i,j;
	for (i=0; i<nNumCluster-1; i++)
	{
		for (j=i+1; j<nNumCluster; j++)
		{
			double dDist = m_pDistFunc->Distance(m_vpMicroClusters[i]->GetCenter(), m_vpMicroClusters[j]->GetCenter());
			if (dDist < dMinDist)
			{
				nIndex1 = i;
				nIndex2 = j;
				dMinDist = dDist;
			}
		}
	}
	// Merge two micro-clusters
	pCluster1 = m_vpMicroClusters[nIndex1];
	pCluster2 = m_vpMicroClusters[nIndex2];
	pCluster1->Merge(pCluster2);
	delete pCluster2;
	m_vpMicroClusters.erase(m_vpMicroClusters.begin() + nIndex2);
	return 0;
}

int CMLCluStream::CheckOutlierMicroCluster(void)
{
	int i;
	for (i=0; i<(int)m_vpMicroClusters.size(); i++)
	{
		CMLCluStreamMicroCluster* pMicroCluster = m_vpMicroClusters[i];
		double dLastTimeStampMean = pMicroCluster->GetLastTimeStampMean(m_nNumLastTimeCheck);
		if (m_nTimeClock - dLastTimeStampMean > m_dMaxTimeStampBelow)
		{
			// Delete the outlier micro-cluster
			delete pMicroCluster;
			m_vpMicroClusters.erase(m_vpMicroClusters.begin() + i);
			i = i -1;
		}
	}
	return 0;
}

int CMLCluStream::SaveSnapshot(CMLCluStreamSnapshot &snap) const
{
	return snap.Create(m_vpMicroClusters);
}

int CMLCluStream::ReleaseMicroClusters()
{
	int i;
	for (i=0; i<(int)m_vpMicroClusters.size(); i++)
	{
		if (m_vpMicroClusters[i] != NULL)
		{
			delete m_vpMicroClusters[i];
			m_vpMicroClusters[i] = NULL;
		}
	}
	m_vpMicroClusters.clear();
	return 0;
}

int CMLCluStream::MacroClustering(int nK, std::vector<CMLDataCluster>& vMacroClusters, const CMLCluStreamSnapshot& snap)
{
	int i;
	vMacroClusters.clear();
	
	// Create the dataset to prepare the clustering
	CMLDataSet centerDataSet;
	std::vector<double> centerWeights;
	std::map<CMLDataPoint, int> centerIndexes;
	std::set<CMLDataPoint> centerSet;
	int nTotalChildrenDataPoints = 0;

	centerDataSet.Resize(snap.GetNumCFs());
	for (i=0; i<snap.GetNumCFs(); i++)
	{
		CMLDataPoint center = snap.GetCenter(i);
		centerDataSet.Set(i, center);
		centerIndexes.insert(std::make_pair(center, i));
		centerSet.insert(center);
		nTotalChildrenDataPoints += snap.GetDataPointCount(i);
	}

	// Calculate the weights for the centers
	centerWeights.resize(snap.GetNumCFs());
	for (i=0; i<snap.GetNumCFs(); i++)
		centerWeights[i] = ((double)(snap.GetDataPointCount(i))) / ((double)nTotalChildrenDataPoints);

	// Clustering this level nodes
	CMLClustering_KMeans kMeans;
	if ((int)centerSet.size() < nK)
		nK = (int)centerSet.size();

	kMeans.SetK(nK);
	std::vector<CMLDataCluster> vClusters;
	int nRet = kMeans.DoClustering(centerDataSet, centerWeights, vClusters);
	ML_ON_FAILED_RETURN(nRet);

	// Collect data points of macro clusters
	vMacroClusters.resize(vClusters.size());
	for (i=0; i<nK; i++)
	{
		vMacroClusters[i].center = vClusters[i].center;
	}

	return 0;
}


